package com.mdnote.practice.dp;

import java.util.Arrays;
import java.util.List;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/20
 * @description 三角形最小路径和
 */
public class LeetCode120 {

    public static void main(String[] args) {
        LeetCode120 leetCode120 = new LeetCode120();
        List<Integer> list1 = Arrays.asList(2);
        List<Integer> list2 = Arrays.asList(3, 4);
        List<Integer> list3 = Arrays.asList(6, 5, 7);
        List<Integer> list4 = Arrays.asList(4, 1, 8, 3);
        List<List<Integer>> list = Arrays.asList(list1, list2, list3, list4);
        int res = leetCode120.minimumTotal(list);
        System.out.println(res);
    }

    public int minimumTotal(List<List<Integer>> triangle) {
        // recursion
        int[][] memo = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
//        int res = recursion(0, 0, memo, triangle);
        // dp
//        int res = dp(triangle);

        int res = dpPlus(triangle);
        return res;
    }

    private int dpPlus(List<List<Integer>> triangle) {

        int[] dp = new int[triangle.get(triangle.size() - 1).size()];
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            dp[i] = triangle.get(triangle.size() - 1).get(i);
        }

        for (int i = triangle.size() - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[j] = triangle.get(i).get(j) + Math.min(dp[j], dp[j + 1]);
            }
        }

        return dp[0];
    }

    /**
     * 分析：
     * 1. 重复子问题：想要求当前节点到最下面的最短路径 = 当前节点的值 + Max(左节点到最下面的路径，右节点到最下面的路径)
     * 2. DP数组： dp[i][j] i 当前层，j 当前层的某个元素 dp[i][j] 当前元素到最下面的最短距离
     * 3. DP方程：dp[i][j] = triangle(i, j) + Max{dp[i + 1][], dp[i + 1][j + 1]};
     * @param triangle
     * @return
     */
    private int dp(List<List<Integer>> triangle) {

        // 初始化DP数组
        int[][] dp = new int[triangle.size()][triangle.get(triangle.size() - 1).size()];
        for (int i = 0; i < triangle.get(triangle.size() - 1).size(); i++) {
            dp[dp.length - 1][i] = triangle.get(triangle.size() - 1).get(i);
        }
        // DP
        for (int i =  dp.length - 2; i >= 0; i--) {
            for (int j = 0; j < triangle.get(i).size(); j++) {
                dp[i][j] = triangle.get(i).get(j) + Math.min(dp[i + 1][j], dp[i + 1][j + 1]);
            }
        }
        return dp[0][0];
    }

    private int recursion(int i, int j, int[][] memo, List<List<Integer>> triangle) {
        // Terminator
        if (i + 1 == triangle.size()) {
            return triangle.get(i).get(j);
        }
        // Process current logic \ dri;; down
        int left = memo[i + 1][j] != 0 ? memo[i + 1][j] : (memo[i + 1][j] = recursion(i + 1, j, memo, triangle));
        int right = memo[i + 1][j + 1] != 0 ? memo[i + 1][j + 1] : (memo[i + 1][j + 1] = recursion(i + 1, j + 1, memo, triangle));

        // restore current data
        return Math.min(left, right) + triangle.get(i).get(j);
    }
}
